
\prob{003A}{123数字黑洞}

任取一正整数$n$，然后按照如下顺序操作：

先求该数各位中有几个偶数，记为$p(n)$；

再求该数各位中有几个奇数，记为$q(n)$；

最后求该数有几位，记为$r(n)$；

将$p(n), q(n), r(n)$三个数排列为一个新的数$\overline{p(n)q(n)r(n)}$。注意，若$p(n) = 0$，则省略最高位的$0$；

将上述所有操作统称为对$n$的\emph{一次操作}。对新的数$\overline{p(n)q(n)r(n)}$重复多次操作。

求证：任何正整数经过有限次操作后都会到达数$123$。
\problabels{yellow/数论, green/证明题}

\subsection{数论证明}

下面约定$n_{k + 1}$是$n_k$经过一次操作后的结果。

\begin{lemma} \label{lemma:003A-even1}
  任意数位不含偶数的数经过最多2次操作后将含偶数。
\end{lemma}

\begin{proof}
  首先对于某数位中不含偶数的数$n_0$，有$p(n_0) = 0, q(n_0) = r(n_0)$，故经过一次操作后得到新数$n_1 = \overline{r(n_0)r(n_0)}$，于是易知其位数$r(n_1)$是偶数，于是再次操作后的新数$n_2$的个位是偶数。
\end{proof}

\begin{lemma} \label{lemma:003A-even2}
  任意数位含偶数的数经过任意次操作后偶数不会消失。
\end{lemma}

\begin{proof}
  对于某含偶数的数$n_0$，经过一次操作后得$n_1 = \overline{p(n_0)q(n_0)r(n_0)}$，其中$p(n_0) + q(n_0) = r(n_0)$。易知$p(n_0), q(n_0), r(n_0)$不可能全为奇数，即其中至少有一个个位是偶数，故$n_1$中含有偶数。由此可推知$n_2, n_3, \dots$均含有偶数。
\end{proof}

引理~\ref{lemma:003A-even1} 与引理~\ref{lemma:003A-even2} 让我们得以只考虑含有偶数的数。因此，下面我们所说的“数”均含有偶数。

接下来，尝试证明所有的数经过有限次操作后可得三位数。

\begin{lemma} \label{lemma:003A-rn13rrn0}
  对于任意数$n_0 > 0$，有
  \[ \max\{r(n_1)\} = 3r(r(n_0)) \]
\end{lemma}

\begin{proof}
  由于$n_1 = \overline{p(n_0)q(n_0)r(n_0)}$，故
  \[ r(n_1) = r(p(n_0)) + r(q(n_0)) + r(r(n_0)) \]
  而$p(n_0) + q(n_0) = r(n_0)$，故
  \[ r(p(n_0)) \le r(r(n_0)), r(q(n_0)) \le r(r(n_0)) \]
  于是易知$\max\{r(n_1)\} = 3r(r(n_0))$。
\end{proof}

\begin{lemma} \label{lemma:003A-3k10k1}
  对于正整数$k > 1$，有$3k < 10^{k - 1}$。
\end{lemma}

\begin{proof}
  参见总第~\ref{sec:0039} 题。
\end{proof}

有了上面的引理，现在开始正式的证明。使用归纳法证明任意位的数经过有限次操作后都可得到三位数。如下：

设原数为$n_0$，对$r(r(n_0))$进行分情况讨论：

若$r(r(n_0)) = 1$，则根据引理~\ref{lemma:003A-rn13rrn0}，有$\max\{r(n_1)\} = 3$，即$n_1$至多为三位数，而$r(n_1) = r(p(n_0)) + r(q(n_0)) + r(r(n_0)) \ge 1 + 1 + 1 = 3$，故$r(n_1) = 3$，$n_1$为三位数。这样，我们顺便证明了三位数经过任意次操作后仍为三位数。

若$r(r(n_0)) > 1$，易知$10^{r(r(n_0)) - 1} \le r(n_0) < 10^{r(r(n_0))}$，故$\min\{r(n_0)\} = 10^{r(r(n_0)) - 1}$。根据引理~\ref{lemma:003A-rn13rrn0}，有$\max\{r(n_1)\} = 3r(r(n_0))$；根据引理~\ref{lemma:003A-3k10k1}，有$3r(r(n_0)) < 10^{r(r(n_0)) - 1}$，即
\begin{align*}
  \max\{r(n_1)\} &< \min\{r(n_0)\} \\
  r(n_1) &< r(n_0)
\end{align*}
可见对满足$r(r(n_0)) > 1$的数$n_0$，经过一次操作，得到的数$n_1$的位数都比$n_0$的位数少。

因此，$r(n_i)$不断减小，直到到达某个$i$，使得$r(r(n_i)) = 1$，此时再最多经过一次操作即可得到三位数。因此，只要证明所有三位数经过有限次操作可得$123$，即可证明原命题。

设得到的三位数是$n_{k - 1} = \overline{ABC}$，其中含有偶数。于是易知经过一次操作后得到的$n_k$是$\overline{PQ3}$的形式，其中$P + Q = 3$。3为奇数，故$P, Q$必然一奇一偶。因此，三位数$\overline{PQ3}$中含有1个偶数，2个奇数，再经过一次操作即得$n_{k + 1} = 123$。

证毕。
